Recent research efforts have produced a generalized packet switched architecture which can be extended to large sizes. The architecture is referred to in the literature as the growable packet switch architecture. This architecture also provides many valuable features besides efficient switch growth. It uses the statistical nature of packet traffic to allow meaningful tradeoffs between overall switch cost, complexity, and delay-and-throughput characteristics. The growable packet switch architecture is described in the article: A Growable Packet Switch Architecture, IEEE Transactions on Communications. February, 1992, by Eng et al. Furthermore, the growable packet switch architecture may provide contention resolution between multiple packets that are destined for the same output port using a technique very similar to that explained in the article: The Knockout Switch, ISS, AT&T Technical Papers, 1987, by Yeh et al. The growable packet switch architecture further requires correct ordering of packets at the output ports as most packet protocols require, but does not specify how that requirement is to be fulfilled. It also permits multicast and broadcast operation, but does not provide any implementation details.
The general growable packet switch architecture is shown in FIG. 1. In FIG. 1, the packet switch 100, has two basic sub-systems: the distribution network 102 and the output packet modules 104. The operation of the packet switch 100 requires that each of the packets arriving at its respective input port be synchronized at the packet level. If the packet switch 100 is for Asynchronous Transfer Mode (which shall be assumed), the packets are referred to as cells. The synchronization is provided for each cell by a respective elastic store 107 inside each interface card 106. Such synchronizations allows the operation of the packet switch 100 to be divided into successive ATM cell intervals. The distribution network 102 of a growable packet switch is memoryless, so it must route each cell that arrives at its inputs within a particular ATM cell interval to any input port on the output packet module that has a connection to the packet's desired output line. Each of the output packet modules 104 includes memory devices which are used to buffer the cells in order to alleviate problems associated with multiple cells destined for the same output line at the same time.
According to the growable packet switch architecture, the only way to reduce cell loss probabilities with fixed link rates is to grow the switch bigger. Consider the example of an N-input, N-output network, such as packet switch 100. If it is to be constructed, it may be built from K output packet modules, where each output packet module 104 has m inputs and n outputs. If the output packet modules 104 have these input-output characteristics, then the distribution network 102 of packet switch 100 must support N input ports, and (Nm/n)=(Km) output lines which are connected to the K=N/n mxn output packet modules 104. The circuitry within each output packet module 104 routes each of the arriving cells within a particular ATM cell interval to one of n FIFOs 110 within its respective output packet module 104. As a result, each of the N output ports has a FIFO 110 associated with it. Once every ATM cell interval, the output packet module 104 extracts a cell from the front of each of the queues within each of its FIFOs 110 and transmits the cell out on the output port associated with the respective FIFO 110. The length of these FIFO queues can be selected to produce any desired queue overflow probability using formulae developed from queuing theory principles.
Although the growable packet switch architecture is an extremely powerful design, if it is strictly followed the only way to reduce cell loss probabilities within the switch typically requires an increase in the hardware cost and complexity of the switch's distribution network or the output module or both.
An interesting feature of the growable packet switch is the manner in which it provides contention resolution between multiple packets that are destined for the same output port. The contention resolution problem is a problem that must be addressed by all packet networks. Typically, some form of arbitration and some form of buffering are required to solve the contention resolution problem. Arbitration is used to determine which of the many input packets will be given priority whenever contention exists. Those packets which are not able to be instantly routed to their desired output are usually buffered at some point in the network, and re-transmitted to their desired output at a later time. In the growable packet switch architecture, the knockout principle mentioned previously is used instead to decrease the number of buffers (FIFO queues) that are required. The knockout principle takes advantage of the statistical nature of packet traffic to determine the number of unique paths that must be provided to each output port to yield desired operating characteristics. As an example of the knockout principle, consider if more than m cells were simultaneously destined for the same mxn output packet module during a particular ATM cell interval. For such a case, only m of the cells can be successfully routed through the distribution network and the rest of the packets must be dropped, i.e. knocked out.
For an N-input, N-output switch 100 comprised of N/n mxn output packet modules 104 and a N.times.(Nm/n) distribution network 102, if R represents the average occupancy on the input links, then the cell loss probability within the distribution network 102 according to Eng et al. is given by: ##EQU1##
These formulae assume that the arriving cell traffic has independent and uniform destination address distributions, so the traffic is uniformly distributed across all of the output ports (and therefore across all of the output packet modules). These formulae also assume that the distribution network 102 is virtually non-blocking, i.e., the probability that an idle input port cannot be connected to an idle output port is much less than the cell loss probability due to the knockout principle.
Various switch designs proposed in the switching system art could be used to realize the distribution network 102 within the growable packet switch architecture shown in FIG. 1. An electronic version of a crossbar switch using discrete or integrated circuit components and multistage Benes and Clos networks are just some of many possible examples. So, to physically realize a packet switch from the growable packet switch architecture requires a lot of techological development. Thus, there is a need in the art for a growable packet switch design that has low cell loss probabilities but is not unduly complex to physically realize.
A related consideration is what type of controller 112 might be used for routing cells within the distribution network 102. Whether controller 112 might be an out-of-band type or an in-band type, which is also known as a self-routing type. The type of controller 112 that might be used has some relationship to how many stages are used.
Path hunt calculations to determine cell routing for in-band controllers are based only on localized traffic information and not on global information regarding all of the switch traffic because of time and hardware considerations for obtaining global information, so the connections selected by an in-band controller may not always be optimal. As a result, networks based on in-band controllers often require substantially more switching fabric (stages and/or nodes) in order to provide the same cell loss probabilities as a comparably sized switch system which uses an out-of-band controller. Thus, there is a need in the an for a growable packet switch that does not use an in-band controller.
The design of an ATM packet switch must provide a means for delaying (temporarily in a deterministic, fixed length FIFO) arriving cells at the packet switch inputs, extracting VPI/VCI information from the cell headers, deriving routing request information from each VPI/VCI value through a look-up table (indicating the cell's desired output port or line), and transmitting this routing request information to the controller 112. The controller 112 must rapidly hunt paths for all of the cells that are arriving at the N input ports. The controller 112 calculates and stores information regarding the current state (busy or idle) of each of the shared resources (links and nodes) within the distribution network 102. This information is commonly stored in a busy-idle table in memory of some sort, which stores one bit of information for each of the links in the network. Once the controller 112 calculates the appropriate paths for each of the cells that have arrived at the inputs, it transmits control information into the distribution network 102 to set up the required paths. The cells in the elastic stores 107 of the packet switch inputs can then be extracted and routed through the distribution network 102. Although memory devices may be used in the elastic stores 107, cells are stored there only for synchronization and path hunt purposes, not for the accommodation of contention between cells. Thus, the distribution network and its input interfaces are `memoryless` within the meaning of that term, i.e. no long term storage to accommodate cell contention.
The growable packet switch 100 uses output queuing to avoid the occurrence of head-of-line blocking. The cells that are temporarily held in the input FIFO do not suffur from head-of-line blocking, because the FIFOs are simply acting as delay lines. The amount of time spent by any cell in an input FIFO is a fixed amount that is known before the cells arrive in the FIFO- it is not at all a function of the traffic in the packet switch 100. It is beneficial to define two new terms associated with the processing and routing of an ATM cell: the arrival interval and the routing interval. The arrival interval the an ATM cell is defined as the ATM cell interval during which the cell arrives at its input line interface card 106. The routing interval for an ATM cell is defined as the ATM cell interval during which the cell is passed from an input line interface card 106 into the distribution network 102. Since the delay incurred in the FIFO 107 of the line card is a known, fixed quantity, there is always a fixed amount of time (.DELTA.T) between the arrival interval and the routing interval for a particular ATM cell. As a result, if a cell arrives during some i-th arrival interval, then it will always be routed through the distribution network during the i-th routing interval. The i-th routing interval always occurs a fixed interval of time .DELTA.T after the i-th arrival interval. The presence of the fixed-length FIFO 107 on the input line interface card permits each arriving ATM cell to be held in its input line interface card 106 until the out-of-band controller 112 sets up a respective path, but ALL cells are held in the FIFO for the same period of time, (except the very minor variances in timing and propagation for which the synchronization is provided).
The number of stages within the distribution network 102 can have a large effect on the complexity of the path hunting that the controller 112 must perform. For example, an s-stage multistage interconnection network requires the controller 112 to locate s+1 idle links in different link-stages to identify a single idle path, so more data must be read from and written to the busy-idle memories of the controller 112 than would be required for a single-stage network, where s=1. Additionally, complicated channel graphs, which are generated by many multi-stage interconnection networks, make partitioning of the distribution network 102 into disjoint units difficult. Partitioning is desirable because it permits path hunting to be performed in parallel for each of the partitioned units. Thus, there is a need in the art for a growable packet switch which has a single-stage partitionable distribution network 102.
FIGS. 2A, 2B and 2C illustrate that there are several types of single-stage networks that could be utilized as the distribution network 102 of the growable packet switch architecture 100. The three illustrated examples are: the crossbar shown in FIG. 2A (of which the electronic integrated circuit crossbar is an example), the splitter-combiner shown in FIG. 2B, and networks constructed from a single stage of many small switching nodes shown in FIG. 2C.
Thus far, it has been assumed that the arriving packet or cell traffic has independent and uniform destination address distributions, so the traffic is uniformly distributed across all of the output ports and all of the output packet modules. For those situations when the arriving packet or cell traffic is not independent and its address distribution is not uniform such that one of the output packet modules 104 has more traffic directed to it than it has inputs, it is desirable to find a way around the cell losses that occur, i.e., knocked out by the contending cells, without greatly increasing the size and cost of the packet switch.
It is an object of the present invention to provide an apparatus that allows a reduction of ATM cell loss probabilities with very little increase in system hardware cost, and a method for operating this apparatus.
It is another object of the present invention to provide a growable packet switch that uses a controller that has global knowledge of the status of all the nodes and connections of the distribution network and output packet module inputs.
It is another object of the present invention to provide a growable packet switch with a controller which rolls path requests that cannot be fulfilled during the present interval into a next interval.